The last decade has seen rapid progress in micro aerial robots, autonomous aerial vehicles that are smaller than 1 meter in scale and 1 kg or less in mass. Winged aircrafts can range from fixed-wing vehicles to flapping-wing vehicles, the latter mostly inspired by insect flight. Rotor crafts, including helicopters, coaxial rotor crafts, ducted fans, quadrotors and hexarotors, have proved to be more mature with quadrotors being the most commonly used aerial platform in robotics research labs. In this class of devices, the Hummingbird quadrotor sold by Ascending Technologies, GmbH, with a tip-to-tip wingspan of 55 cm, a height of 8 cm, mass of about 500 grams including a Lithium Polymer battery and consuming about 75 Watts, is a remarkably capable and robust platform.
Multi-rotor aerial vehicles have become increasingly popular robotic platforms because of their mechanical simplicity, dynamic capabilities, and suitability for both indoor and outdoor environments. In particular, there have been many recent advances in the design, control and planning for quadrotors, rotorcrafts with four rotors. As will be explained below, the invention relates to a method for generating optimal trajectories for heterogeneous quadrotor teams like those shown in FIG. 1 in environments with obstacles.
Micro aerial robots have a fundamental payload limitation that is difficult to overcome in many practical applications. However, larger payloads can be manipulated and transported by multiple UAVs either using grippers or cables. Applications such as surveillance or search and rescue that require coverage of large areas or imagery from multiple sensors can be addressed by coordinating multiple UAVs, each with different sensors.
Trajectories that quadrotors can follow quickly and accurately should be continuous up to the third derivative of position (or C 3). This is because, for quadrotors, discontinuities in lateral acceleration require instantaneous changes in roll and pitch angles and discontinuities in lateral jerk require instantaneous changes in angular velocity. Finding C 3 trajectories requires planning in a high-dimensional search space that is impractical for methods using reachability algorithms, incremental search techniques or LQR-tree-based searches. The problem is exacerbated when planning for multiple vehicles as this further expands the dimension of the search space.
The invention addresses the issue of scaling down the quadrotor platform to develop a truly small micro UAV. The most important and obvious benefit of scaling down in size is the ability of the quadrotor to operate in tightly constrained environments in tight formations. While the payload capacity of the quadrotor falls dramatically, it is possible to deploy multiple quadrotors that cooperate to overcome this limitation. Again, the small size is beneficial because smaller vehicles can operate in closer proximity than large vehicles. Another interesting benefit of scaling down is agility. Smaller quadrotors exhibit higher accelerations allowing more rapid adaptation to disturbances and higher stability.
Prior work by the inventors showed that the dynamic model for the quadrotor is differentially flat. The inventors use this fact to derive a trajectory generation algorithm that allows one to naturally embed constraints on desired positions, velocities, accelerations, jerks and inputs while satisfying requirements on smoothness of the trajectory. The inventors extend that method in accordance with the present invention to include multiple quadrotors and obstacles. The method allows for different sizes, capabilities, and varying dynamic effects between different quadrotors. The inventors enforce collision avoidance using integer constraints which transforms their quadratic program (QP) from into a mixed-integer quadratic program (MIQP).
Prior work by the inventors also draws from the extensive literature on mixed-integer linear programs (MILPs) and their application to trajectory planning from Schouwenaars et al., “Decentralized Cooperative Trajectory Planning of Multiple Aircraft with Hard Safety Guarantees,” Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, Providence, R.I., August 2004. The methods described herein build upon such work.